#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.InteropServices;
using System.Threading;
using System.Xml;
using System.Xml.Schema;
using System.Xml.Serialization;
using AbstractClass.Linq;

namespace AbstractClass.Collections.Generic
{
    /// <summary>
    /// Represents a first-in, first-out collection of objects sorted by their priorities.
    /// </summary>
    /// <typeparam name = "TPriority">Specifies the type of priorities of the elements in the queue.</typeparam>
    /// <typeparam name = "TValue">Specifies the type of elements in the queue.</typeparam>
    [Serializable, DebuggerDisplay("Count = {Count}")]
    public sealed class PriorityQueue<TPriority, TValue> : ICollection<KeyValuePair<TPriority, TValue>>, ICollection,
                                                           IXmlSerializable
    {
        #region Declaration

        private static readonly TPriority[] EmptyKeys;
        private static readonly TValue[] EmptyValues;
        private readonly IComparer<TPriority> _comparer;
        private TValue[] _array;
        private int _head;
        private TPriority[] _keys;

        [NonSerialized] private object _syncRoot;
        private int _tail;
        private int _version;

        #endregion

        #region Constructors

        static PriorityQueue()
        {
            EmptyKeys = new TPriority[0];
            EmptyValues = new TValue[0];
        }

        /// <summary>
        ///   Initializes a new instance of the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   class.
        /// </summary>
        public PriorityQueue()
        {
            _keys = EmptyKeys;
            _array = EmptyValues;
            Count = 0;
            _comparer = Comparer<TPriority>.Default;
        }

        /// <summary>
        ///   Initializes a new instance of the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   class.
        /// </summary>
        /// <param name = "collection">The collection whose elements are copied to the new <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   .</param>
        /// <exception cref = "ArgumentNullException"><paramref name="collection"/> is null.</exception>
        public PriorityQueue(IEnumerable<KeyValuePair<TPriority, TValue>> collection)
            : this()
        {
            if (_comparer != null)
            {
                _comparer = Comparer<TPriority>.Default;
            }

            if (collection == null)
            {
                throw new ArgumentNullException("collection");
            }

            _array = new TValue[4];
            Count = 0;
            _version = 0;
            using (IEnumerator<KeyValuePair<TPriority, TValue>> enumerator1 = collection.GetEnumerator())
            {
                while (enumerator1.MoveNext())
                {
                    Enqueue(enumerator1.Current.Value, enumerator1.Current.Key);
                }
            }
        }

        /// <summary>
        ///   Initializes a new instance of the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   class.
        /// </summary>
        /// <param name = "capacity">The initial number of elements that the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   can contain.</param>
        /// <exception cref = "ArgumentOutOfRangeException"><paramref name="capacity"/> is less than zero.</exception>
        public PriorityQueue(int capacity)
        {
            if (capacity < 0)
            {
                throw new ArgumentOutOfRangeException("capacity", LanguageResource.NeedNonNegativeNumber);
            }

            _array = new TValue[capacity];
            _keys = new TPriority[capacity];
            _head = 0;
            _tail = 0;
            Count = 0;

            _comparer = Comparer<TPriority>.Default;
        }

        /// <summary>
        ///   Initializes a new instance of the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   class.
        /// </summary>
        /// <param name = "capacity">The initial number of elements that the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   can contain.</param>
        /// <param name = "comparer">The <see cref = "IComparer&lt;TPriority&gt;" />
        ///   implementation to use when comparing keys-or-null to use the default <see cref = "Comparer" />
        ///   for the type of the key.</param>
        /// <exception cref = "ArgumentOutOfRangeException"><paramref name="capacity"/> is less than zero.</exception>
        public PriorityQueue(int capacity, IComparer<TPriority> comparer)
            : this(comparer)
        {
            _array = new TValue[capacity];
            _keys = new TPriority[capacity];
            _head = 0;
            _tail = 0;
            Count = 0;
        }

        /// <summary>
        ///   Initializes a new instance of the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   class.
        /// </summary>
        /// <param name = "comparer">The <see cref = "IComparer&lt;TPriority&gt;" />
        ///   implementation to use when comparing keys-or-null to use the default <see cref = "Comparer" />
        ///   for the type of the key.</param>
        public PriorityQueue(IComparer<TPriority> comparer)
        {
            _comparer = comparer;
        }

        #endregion

        #region Public Fields

        /// <summary>
        ///   Gets the <see cref = "IComparer&lt;TPriority&gt;"></see> for the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   .
        /// </summary>
        /// <value>The comparer.</value>
        /// <returns>The <see cref = "IComparable" />
        ///   for the current <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   .</returns>
        public IComparer<TPriority> Comparer
        {
            get { return _comparer; }
        }

        /// <summary>
        ///   Gets the number of elements contained in the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;"/>.
        /// </summary>
        /// <value>The count.</value>
        /// <returns>The number of elements contained in the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;"/>.</returns>
        public int Count { get; private set; }

        /// <summary>
        ///   Removes all objects from the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   .
        /// </summary>
        public void Clear()
        {
            if (_head < _tail)
            {
                Array.Clear(_array, _head, Count);
            }
            else
            {
                Array.Clear(_array, _head, _array.Length - _head);
                Array.Clear(_array, 0, _tail);
            }
            _head = 0;
            _tail = 0;
            Count = 0;
            _version++;
        }

        /// <summary>
        ///   Adds an object to the end of the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   .
        /// </summary>
        /// <param name = "value">The object to add to the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   . The value can be null for reference types.</param>
        /// <param name = "priority">The key to add to the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   . The value can't be null</param>
        public void Enqueue(TValue value, TPriority priority)
        {
            if (Count == _array.Length)
            {
                var num1 = (int) ((_array.Length * 200) / ((long) 100));
                if (num1 < (_array.Length + 4))
                {
                    num1 = _array.Length + 4;
                }
                SetCapacity(num1);
            }
            InsertElement(value, priority);
            Count++;
            _version++;
        }

        /// <summary>
        ///   Removes and returns the object at the beginning of the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   . It is the object of highest priority.
        /// </summary>
        /// <returns>
        ///   The object that is removed from the beginning of the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   .
        /// </returns>
        /// <exception cref = "InvalidOperationException">The <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   is empty.</exception>
        public TValue Dequeue()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException(LanguageResource.PriorityQueueDequeueEmptyQueue);
            }
            TValue local1 = _array[_head];
            _array[_head] = default(TValue);
            _keys[_head] = default(TPriority);
            Array.Sort(_keys, _array, _comparer);
            Array.Reverse(_array);
            Array.Reverse(_keys);
            _head = Head;
            Count--;
            _version++;
            return local1;
        }

        /// <summary>
        ///   Determines whether an element is in the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   .
        /// </summary>
        /// <param name = "item">The object to locate in the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   . The value can be null for reference types.</param>
        /// <returns>
        ///   <c>true</c> if item is found in the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   ; otherwise, <c>false</c>.
        /// </returns>
        public bool Contains(TValue item)
        {
            int num1 = _head;
            int num2 = Count;
            EqualityComparer<TValue> comparer = EqualityComparer<TValue>.Default;
            while (num2-- > 0)
            {
                if (item.Equals(default(TValue)))
                {
                    if (_array[num1].Equals(default(TValue)))
                    {
                        return true;
                    }
                }
                else if ((_array[num1].Equals(default(TValue))) && comparer.Equals(_array[num1], item))
                {
                    return true;
                }
                num1 = (num1 + 1) % _array.Length;
            }
            return false;
        }

        /// <summary>
        ///   Copies the elements of <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   to an existing one-dimensional <see cref = "Array" />
        ///   , starting at the specified array index.
        /// </summary>
        /// <param name = "array">The one-dimensional <see cref = "Array" />
        ///   that is the destination of the elements copied from <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   . The <see cref = "Array" />
        ///   must have zero-based indexing.</param>
        /// <param name = "arrayIndex">The zero-based index in array at which copying begins.</param>
        /// <exception cref = "ArgumentOutOfRangeException"><paramref name="arrayIndex"/> is less than zero.</exception>
        /// <exception cref = "ArgumentNullException"><paramref name="array"/> is null.</exception>
        /// <exception cref = "ArgumentException"><paramref name="arrayIndex"/> is equal to or greater than the length of array or the number of elements in the source <see cref = "PriorityQueue&lt;TPriority,TValue&gt;"></see> is greater than the available space from index to the end of the destination array.</exception>
        public void CopyTo(TValue[] array, int arrayIndex)
        {
            if (array == null)
            {
                throw new ArgumentNullException("array");
            }
            if ((arrayIndex < 0) || (arrayIndex > array.Length))
            {
                throw new ArgumentOutOfRangeException("arrayIndex", LanguageResource.PriorityQueueIndexOutOfRange);
            }
            int num1 = array.Length;
            if ((num1 - arrayIndex) < Count)
            {
                throw new ArgumentException(LanguageResource.InvalidArrayIndex);
            }
            int num2 = ((num1 - arrayIndex) < Count) ? (num1 - arrayIndex) : Count;
            Array.Sort(_keys, _array, _comparer);
            if (num2 == 0) return;
            int num3 = ((_array.Length - _head) < num2) ? (_array.Length - _head) : num2;
            Array.Copy(_array, _head, array, arrayIndex, num3);
            num2 -= num3;
            if (num2 > 0)
            {
                Array.Copy(_array, 0, array, (arrayIndex + _array.Length) - _head, num2);
            }
        }

        /// <summary>
        ///   Copies the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   elements to a new array.
        /// </summary>
        /// <returns>
        ///   A new array containing elements copied from the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   . The elements are sorted.
        /// </returns>
        public TValue[] ToArray()
        {
            var localArray1 = new TValue[Count];
            if (Count != 0)
            {
                if (_head < _tail)
                {
                    Array.Copy(_array, _head, localArray1, 0, Count);
                    return localArray1;
                }
                Array.Copy(_array, _head, localArray1, 0, _array.Length - _head);
                Array.Copy(_array, 0, localArray1, _array.Length - _head, _tail);
            }
            return localArray1;
        }

        /// <summary>
        ///   Returns the object at the beginning of the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   without removing it. The object is of highest priority.
        /// </summary>
        /// <returns>
        ///   The object at the beginning of the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   .
        /// </returns>
        /// <exception cref = "InvalidOperationException">The <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   is empty.</exception>
        public TValue Peek()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException(LanguageResource.PriorityQueueDequeueEmptyQueue);
            }
            TValue val = _array[(Head)];
            return val;
        }

        /// <summary>
        ///   Sets the capacity to the actual number of elements in the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;" />
        ///   , if that number is less than 90 percent of current capacity.
        /// </summary>
        public void TrimExcess()
        {
            var num1 = (int) (_array.Length * 0.9);
            if (Count < num1)
            {
                SetCapacity(Count);
            }
        }

        /// <summary>
        /// Gets the priority associated with the <paramref name="value"/>.
        /// </summary>
        /// <param name="value">The specified value whose priority need to be found.</param>
        /// <returns>Priority associated with <paramref name="value"/>.</returns>
        public TPriority GetPriority(TValue value)
        {
            int index = _array.IndexOf(value);
            return _keys[index];
        }

        #endregion

        #region Private Methods

        // Returns the index of the element with the key given.
        private int Head
        {
            get { return IndexOfKey(MaximumKey()); }
        }

        internal int IndexOfKey(TPriority key)
        {
            if (key.Equals(default(TPriority)))
            {
                throw new ArgumentNullException("key");
            }

            int num1 = Array.IndexOf(_keys, key, 0);
            if (num1 < 0)
            {
                return -1;
            }
            return num1;
        }

        // Returns the index of the element given.
        internal int IndexOfValue(TValue value)
        {
            return Array.IndexOf(_array, value, 0, Count);
        }

        // Returns the object of corresponding index
        internal KeyValuePair<TPriority, TValue> GetElement(int i)
        {
            TValue val = _array[(_head + i) % _array.Length];
            TPriority key = _keys[(_head + i) % _array.Length];
            var ret = new KeyValuePair<TPriority, TValue>(key, val);
            return ret;
        }

        // Reallocate memory to re-dimension the queue with given capacity.
        private void SetCapacity(int capacity)
        {
            var localArray1 = new TValue[capacity];
            var localArray2 = new TPriority[capacity];
            if (Count > 0)
            {
                if (_head < _tail)
                {
                    Array.Copy(_array, _head, localArray1, 0, Count);
                    Array.Copy(_keys, _head, localArray2, 0, Count);
                }
                else
                {
                    Array.Copy(_array, _head, localArray1, 0, _array.Length - _head);
                    Array.Copy(_array, 0, localArray1, _array.Length - _head, _tail);

                    Array.Copy(_keys, _head, localArray2, 0, _keys.Length - _head);
                    Array.Copy(_keys, 0, localArray2, _keys.Length - _head, _tail);
                }
            }
            _array = localArray1;
            _keys = localArray2;
            _head = 0;
            _tail = Count;
            _version++;
        }

        private void InsertElement(TValue value, TPriority key)
        {
            var tempkey = new TPriority[_keys.Length];
            var tempvalue = new TValue[_keys.Length];
            int count = 0;

            for (int i = 0; i < Count; i++)
            {
                tempkey[count] = _keys[i];
                tempvalue[count] = _array[i];
                count++;
            }
            tempkey[count] = key;
            tempvalue[count] = value;
            Array.Copy(tempkey, _keys, _keys.Length);
            Array.Copy(tempvalue, _array, _array.Length);
            Array.Sort(_keys, _array);
            Array.Reverse(_keys);
            Array.Reverse(_array);
            _head = Head;
        }

        private TPriority MaximumKey()
        {
            TPriority[] max = {default(TPriority)};
            foreach (TPriority t in _keys.Where(t => Comparer<TPriority>.Default.Compare(t, max[0]) > 0))
            {
                max[0] = t;
            }
            return max[0];
        }

        #endregion

        #region Interface Implementation

        #region ICollection Members

        /// <summary>
        ///   Gets a value indicating whether access to the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;"/> is synchronized (thread safe).
        /// </summary>
        /// <value></value>
        /// <returns><c>true</c> if access to the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;"/> is synchronized (thread safe); otherwise, <c>false</c>.
        /// </returns>
        public bool IsSynchronized
        {
            get { return false; }
        }

        /// <summary>
        ///   Gets an object that can be used to synchronize access to the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;"/>.
        /// </summary>
        /// <value></value>
        /// <returns>
        ///   An object that can be used to synchronize access to the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;"/>.
        /// </returns>
        public object SyncRoot
        {
            get
            {
                if (_syncRoot == null)
                {
                    Interlocked.CompareExchange(ref _syncRoot, new object(), null);
                }
                return _syncRoot;
            }
        }

        void ICollection.CopyTo(Array array, int arrayIndex)
        {
            if (array == null)
            {
                throw new ArgumentNullException("array");
            }
            if (array.Rank != 1)
            {
                throw new ArgumentException(LanguageResource.PriorityQueueCopyToMultidimensionalArrayIsNotSupported);
            }
            if (array.GetLowerBound(0) != 0)
            {
                throw new ArgumentException(LanguageResource.PriorityQueueCopyToNonZeroLowerBound);
            }
            if ((arrayIndex < 0) || (arrayIndex > array.Length))
            {
                throw new ArgumentOutOfRangeException("arrayIndex", LanguageResource.ArrayIndexMustBeNonNegative);
            }
            if ((array.Length - arrayIndex) < Count)
            {
                throw new ArgumentException(LanguageResource.ArrayOffsetIsTooSmall);
            }

            var pairArray1 = array as KeyValuePair<TPriority, TValue>[];
            if (pairArray1 != null)
            {
                for (int num1 = 0; num1 < Count; num1++)
                {
                    pairArray1[num1 + arrayIndex] = new KeyValuePair<TPriority, TValue>(_keys[num1], _array[num1]);
                }
            }
            else
            {
                var objArray1 = array as object[];
                if (objArray1 == null)
                {
                    throw new ArgumentException(LanguageResource.PriorityQueueCopyToInvalidArrayType);
                }
                try
                {
                    for (int num2 = 0; num2 < Count; num2++)
                    {
                        objArray1[num2 + arrayIndex] = new KeyValuePair<TPriority, TValue>(_keys[num2], _array[num2]);
                    }
                }
                catch (ArrayTypeMismatchException)
                {
                    throw new ArgumentException(LanguageResource.PriorityQueueCopyToInvalidArrayType);
                }
            }
        }

        int ICollection.Count
        {
            get { return Count; }
        }

        #endregion

        #region ICollection<KeyValuePair<TPriority,TValue>> Members

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this, 1);
        }

        IEnumerator<KeyValuePair<TPriority, TValue>> IEnumerable<KeyValuePair<TPriority, TValue>>.GetEnumerator()
        {
            return new Enumerator(this, 1);
        }

        void ICollection<KeyValuePair<TPriority, TValue>>.CopyTo(KeyValuePair<TPriority, TValue>[] array, int arrayIndex)
        {
            if (array == null)
            {
                throw new ArgumentNullException("array");
            }
            int num1 = array.Length;
            if ((arrayIndex < 0) || (arrayIndex > num1))
            {
                throw new ArgumentOutOfRangeException("arrayIndex", LanguageResource.ArrayIndexMustBeNonNegative);
            }
            if ((num1 - arrayIndex) < Count)
            {
                throw new ArgumentException(LanguageResource.ArrayOffsetIsTooSmall);
            }
            if (array.GetLowerBound(0) != 0)
            {
                throw new ArgumentException(LanguageResource.ArrayOffsetIsTooSmall);
            }

            for (int num2 = 0; num2 < Count; num1++, num2++)
            {
                var pair1 = new KeyValuePair<TPriority, TValue>(_keys[num2], _array[num2]);
                array[arrayIndex + num2] = pair1;
            }
        }

        bool ICollection<KeyValuePair<TPriority, TValue>>.Contains(KeyValuePair<TPriority, TValue> keyValuePair)
        {
            int num1 = IndexOfKey(keyValuePair.Key);
            return (num1 >= 0) && EqualityComparer<TValue>.Default.Equals(_array[num1], keyValuePair.Value);
        }

        void ICollection<KeyValuePair<TPriority, TValue>>.Add(KeyValuePair<TPriority, TValue> keyValuePair)
        {
            Enqueue(keyValuePair.Value, keyValuePair.Key);
        }

        bool ICollection<KeyValuePair<TPriority, TValue>>.Remove(KeyValuePair<TPriority, TValue> keyValuePair)
        {
            int num1 = IndexOfKey(keyValuePair.Key);
            if ((num1 >= 0) && EqualityComparer<TValue>.Default.Equals(_array[num1], keyValuePair.Value))
            {
                Dequeue();
                return true;
            }
            return false;
        }

        int ICollection<KeyValuePair<TPriority, TValue>>.Count
        {
            get { return Count; }
        }

        /// <summary>
        ///   Gets a value indicating whether this instance is read only.
        /// </summary>
        /// <value>
        ///   <c>true</c> if this instance is read only; otherwise, <c>false</c>.
        /// </value>
        public bool IsReadOnly
        {
            get { return false; }
        }

        #endregion

        /// <summary>
        ///   Gets the enumerator to iterate in the <see cref = "PriorityQueue&lt;TPriority,TValue&gt;"/>.
        /// </summary>
        /// <returns>
        /// A <see cref = "IEnumerator&lt;T&gt;" /> that can be used to iterate through the collection.
        /// </returns>
        public IEnumerator<KeyValuePair<TPriority, TValue>> GetEnumerator()
        {
            return new Enumerator(this, 1);
        }

        #endregion

        #region Enumerator Implementation

        [Serializable, StructLayout(LayoutKind.Sequential)]
        private struct Enumerator : IEnumerator<KeyValuePair<TPriority, TValue>>
        {
            private readonly PriorityQueue<TPriority, TValue> _priorityQueue;
            private TPriority key;
            private TValue value;
            private int index;
            private readonly int version;
            private readonly int getEnumeratorRetType;

            internal Enumerator(PriorityQueue<TPriority, TValue> priorityQueue, int getEnumeratorRetType)
            {
                _priorityQueue = priorityQueue;
                index = 0;
                version = _priorityQueue._version;
                this.getEnumeratorRetType = getEnumeratorRetType;
                key = default(TPriority);
                value = default(TValue);
            }

            public void Dispose()
            {
                index = 0;
                key = default(TPriority);
                value = default(TValue);
            }

            public bool MoveNext()
            {
                if (version != _priorityQueue._version)
                {
                    throw new InvalidOperationException(LanguageResource.EnumerationFailed);
                }
                if (index < _priorityQueue.Count)
                {
                    key = _priorityQueue._keys[index];
                    value = _priorityQueue._array[index];
                    index++;
                    return true;
                }
                index = _priorityQueue.Count + 1;
                key = default(TPriority);
                value = default(TValue);
                return false;
            }

            public KeyValuePair<TPriority, TValue> Current
            {
                get { return new KeyValuePair<TPriority, TValue>(key, value); }
            }

            object IEnumerator.Current
            {
                get
                {
                    if ((index == 0) || (index == (_priorityQueue.Count + 1)))
                    {
                        throw new InvalidOperationException(LanguageResource.EnumerationOperationCantHappen);
                    }
                    if (getEnumeratorRetType == 2)
                    {
                        return new DictionaryEntry(key, value);
                    }
                    return new KeyValuePair<TPriority, TValue>(key, value);
                }
            }

            void IEnumerator.Reset()
            {
                if (version != _priorityQueue._version)
                {
                    throw new InvalidOperationException(LanguageResource.EnumerationFailed);
                }
                index = 0;
                key = default(TPriority);
                value = default(TValue);
            }
        }

        #endregion

        #region Implementation of IXmlSerializable

        /// <summary>
        ///   This method is reserved and should not be used. When implementing the IXmlSerializable interface, you should return null (Nothing in Visual Basic) from this method, and instead, if specifying a custom schema is required, apply the <see cref = "XmlSchemaProviderAttribute" /> to the class.
        /// </summary>
        /// <returns>
        ///   An <see cref = "XmlSchema" /> that describes the XML representation of the object that is produced by the <see cref = "M:System.Xml.Serialization.IXmlSerializable.WriteXml(System.Xml.XmlWriter)" /> method and consumed by the <see cref = "M:System.Xml.Serialization.IXmlSerializable.ReadXml(System.Xml.XmlReader)" /> method.
        /// </returns>
        XmlSchema IXmlSerializable.GetSchema()
        {
            return null;
        }

        /// <summary>
        ///   Generates a new <see cref = "PriorityQueue&lt;TPriority,TValue&gt;"/> object from its XML representation.
        /// </summary>
        /// <param name = "reader">The <see cref = "XmlReader" /> stream from which the object is deserialized.</param>
        void IXmlSerializable.ReadXml(XmlReader reader)
        {
            var keySerializer = new XmlSerializer(typeof (TPriority));
            var valueSerializer = new XmlSerializer(typeof (TValue));

            bool wasEmpty = reader.IsEmptyElement;
            reader.Read();

            if (wasEmpty)
                return;

            while (reader.NodeType != XmlNodeType.EndElement)
            {
                reader.ReadStartElement("item");
                reader.ReadStartElement("key");

                var key = (TPriority) keySerializer.Deserialize(reader);
                reader.ReadEndElement();

                reader.ReadStartElement("value");
                var value = (TValue) valueSerializer.Deserialize(reader);
                reader.ReadEndElement();
                Enqueue(value, key);
                reader.ReadEndElement();
                reader.MoveToContent();
            }
            reader.ReadEndElement();
        }

        /// <summary>
        ///   Converts a <see cref = "PriorityQueue&lt;TPriority,TValue&gt;"/> object into its XML representation.
        /// </summary>
        /// <param name = "writer">The <see cref = "XmlWriter" /> stream to which the object is serialized.</param>
        void IXmlSerializable.WriteXml(XmlWriter writer)
        {
            var keySerializer = new XmlSerializer(typeof (TPriority));
            var valueSerializer = new XmlSerializer(typeof (TValue));
            int count = 0;

            foreach (TPriority key in _keys)
            {
                writer.WriteStartElement("item");
                writer.WriteStartElement("key");
                keySerializer.Serialize(writer, key);
                writer.WriteEndElement();
                writer.WriteStartElement("value");
                TValue value = _array[count];
                valueSerializer.Serialize(writer, value);
                writer.WriteEndElement();
                writer.WriteEndElement();
                count++;
            }
        }

        #endregion
    }
}